<!DOCTYPE html>
<html class="no-js" lang="zh">
  <head>
<meta charset="utf-8">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<link rel="alternate" href="https://www.desgard.com" hreflang="pt-BR">
<link href="http://gmpg.org/xfn/11" rel="profile">
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="theme-color" content="#005344">
<title>Guardia · 瓜地</title>
<meta name="google-site-verification" content="zS1dSn20XtA4FJYEOQLXqI0boxZdMnJ2g3beje-cl20">
<meta name="description" content="I write many code to write less code.💻">
<meta name="keywords" content="">
<!-- Social: Facebook / Open Graph -->
<meta property="og:url" content="https://www.desgard.com/CFArray/">
<meta property="og:title" content="       CFArray 的历史渊源及实现原理 | Gua  ">
<meta property="og:description" content="I write many code to write less code.💻">
<meta property="og:site_name" content="Desgard_Duan">
<meta property="og:locale" content="pt_BR">
<meta property="og:type" content="website">
<meta property="og:author" content="https://www.facebook.com/desgard.duan">
<meta property="og:image" content="https://www.desgard.com">
<!-- Social: Twitter -->
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:site" content="@nandomoreirame">
<meta name="twitter:domain" content="https://www.desgard.com">
<meta name="twitter:title" content="       CFArray 的历史渊源及实现原理 | Gua  ">
<meta name="twitter:description" content="I write many code to write less code.💻">
<meta name="twitter:image:src" content="https://www.desgard.com">
<!-- Favicons -->
<link rel="apple-touch-icon" sizes="114x114" href="https://www.desgard.com/assets/ico/apple-touch-icon-114-516f4e19976b9e4dbb77ad9b576831fe.png">
<link rel="apple-touch-icon" sizes="72x72" href="https://www.desgard.com/assets/ico/apple-touch-icon-72-5409b2df229305703caf583d86c845ab.png">
<link rel="apple-touch-icon" href="https://www.desgard.com/assets/ico/apple-touch-icon-57-aa873e019cf659e0d4e6a0b5bb9f379d.png">
<link rel="shortcut icon" href="https://www.desgard.com/assets/ico/favicon-4298be3d3fbe23e18d65bded9d930899.png">
<!-- rel prev and next -->
<!-- Canonical link tag -->
<link rel="canonical" href="https://www.desgard.com/CFArray/">
<link rel="alternate" type="application/rss+xml" title="Gua" href="https://www.desgard.com/feed.xml">
<link rel="stylesheet" href="/assets/main-0b7b828712f4c43b75bba4861c907bb1.css">
<script src="/assets/modernizr-custom-cb807611a3e262b2eac59444cbab74d6.js" data-cfasync="false"></script>
<script src="/assets/js/jquery-3.1.js"></script>
<script src="/assets/js/jquery.rotate.js"></script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="application/ld+json">
{
  "@context": "http://schema.org",
  "@type": "Website",
  "publisher": "www.desgard.com",
  "url": "http://www.desgard.com/",
  "description": "瓜地"
}
</script>
<script type="text/javascript">
  var disqus_shortname = 'desgard',
      baseurl          = '';
</script>
<!--
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-52446115-1']);
_gaq.push(['_trackPageview']);
(function() {
  var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
  ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
  var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>-->
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "//hm.baidu.com/hm.js?c5a8123bc51782a3083a631ed9ff50e4";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'] ],
        displayMath: [ ['$$','$$'] ],
        processEscapes: true
      }
    });
  </script>
  </head>
  <body class="post-template single">
    <header class="header">
  <div class="container">
    <h1><a href="/"><strong>desgard</strong>.com</a></h1>
    <nav class="navbar">
      <ul>
        <li><a href="/">Home</a></li>
        <li><a href="#!" data-modal="modalSearch"><i class="fa fa-search"></i></a></li>
        <li><a href="/comment " target="_blank"><i class="fa fa-comments"></i></a></li>
        <li><a href="/feed.xml" target="_blank"><i class="fa fa-feed"></i></a></li>
      </ul>
    </nav>
  </div>
</header>
    <main class="wrapper container" itemprop="mainContentOfPage" itemscope="itemscope" itemtype="http://schema.org/Blog">
      <article class="post" itemscope="itemscope" itemtype="http://schema.org/BlogPosting" itemprop="blogPost">
  <header class="post-header">
    <h1>CFArray 的历史渊源及实现原理</h1>
    <div class="post-meta">
      <time datetime="2015-10-13">
        <i class="fa fa-calendar-o"></i> <time datetime="2017-02-02"> 2017-02-02
      </time>
      <span>
        <i class="fa fa-comments"></i> <a href="#container">Comment me!</a>
      </span>
      <span>
<!--
        <i class="fa fa-folder-open-o"></i> 
-->
      </span>
    </div>
  </header>
  <p>在 iOS 开发中，<code>NSArray</code> 是一个很重要的数据结构。尤其 TableView 中的数据缓存与更新， <code>NSArray</code> 来缓存数据以及对于显示数据的修改操作。而在 Core Foundation 中 <code>CFArray</code> 与 <code>NSArray</code> 相互对应，这引起了笔者对 Core Foundation 和 Foundation 库中的原生数据结构实现产生兴趣，所以来研究一下。</p>
<h2 id="cfarray-">CFArray 历史渊源</h2>
<p><code>NSArray</code> 和 <code>CFArray</code> 是 <strong>Toll-Free Bridged</strong> 的，在 <a href="http://opensource.apple.com/">opensource.apple.com</a> 中， <code>CFArray</code> 是开源的。这更有助于我们的学习与研究。在 <a href="http://blog.ibireme.com/2014/02/17/cfarray/">Garan no Dou</a> 大神之前在做个人工具库的时候，曾经研究过 <code>CFArray</code> 的历史渊源和实现手段，在阅读此文之前可以参考一下前辈的优秀博文。</p>
<p><em><a href="http://ridiculousfish.com/blog/posts/array.html">Array</a></em> 这篇 2005 年的早期文献中，最早介绍过 <code>CFArray</code> ，并且测试过其性能水平。它将 <code>CFArray</code> 和 STL 中的 <code>Vector</code> 容器进行了性能对比，由于后者的实现我们可以理解成是对 C 中的数组封装，所以在性能图上大多数操作都是线性的。而在 <code>CFArray</code> 的图中，会发现很多不一样的地方。</p>
<p><img src="http://7xwh85.com1.z0.glb.clouddn.com/vector_results.jpg" alt="vector_results" /></p>
<p><img src="http://7xwh85.com1.z0.glb.clouddn.com/cfarray_results.jpg" alt="cfarray_results" /></p>
<p>上图分析可以看出， <code>CFArray</code> 在头插、尾插插入时候的效率近乎常数，而对于中间元素的操作会从小数据的线性效率在一个阈值上突然转变成线性效率，而这个跃变灰不由得想起在 Java 8 当中的 <code>HashMap</code> 的数据结构转变方式。</p>
<p>在 ObjC 的初期，<code>CFArray</code> 是使用 <em>deque 双端队列</em> 实现，所以会呈现出头尾操作高效，而中间操作成线性的特点。在容量超过 300000 左右时（实际应该是 262140 = 2^18 ），时间复杂度发生陡变。在源代码中，阈值被宏定义为 <code>__CF_MAX_BUCKETS_PER_DEQUE</code> ，具体代码可以见 <em><a href="http://opensource.apple.com/source/CF/CF-550/CFArray.c">CF-550-CFArray.c</a></em> （2011 年版本）：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="k">if</span> <span class="p">(</span><span class="n">__CF_MAX_BUCKETS_PER_DEQUE</span> <span class="o">&lt;=</span> <span class="n">futureCnt</span><span class="p">)</span> <span class="p">{</span>
    <span class="sr">//</span> <span class="err">创建</span> <span class="no">CFStorage</span> <span class="err">引用</span>
    <span class="no">CFStorageRef</span> <span class="n">store</span>
    <span class="sr">//</span> <span class="err">转换</span> <span class="no">CFArray</span> <span class="err">为</span> <span class="no">Storage</span>
    <span class="n">__CFArrayConvertDequeToStore</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="n">store</span> <span class="o">=</span> <span class="p">(</span><span class="no">CFStorageRef</span><span class="p">)</span><span class="n">array</span><span class="o">-&gt;</span><span class="n">_store</span><span class="p">;</span>
<span class="p">}</span></code></pre></div>
<p>可以看到，当数据超出阈值 <code>__CF_MAX_BUCKETS_PER_DEQUE</code> 的时候，会将数据结构从 <code>CFArray</code> 转换成 <code>CFStorage</code> 。 <code>CFStorage</code> 是一个平衡二叉树的结构，为了维护数组的顺序访问，将 Node 的权值使用下标完成插入和旋转操作。具体的体现可以看 <code>CFStorageInsertValues</code> 操作。具体代码可以查看 <a href="http://opensource.apple.com/source/CF/CF-368.18/Collections.subproj/CFStorage.c">CF-368.18-CFStorage.c</a> 。</p>
<p>在 2011 年以后的 <a href="http://opensource.apple.com/source/CF/CF-635.15/CFArray.c">CF-635.15-CFArray.c</a> 版本中， <code>CFArray</code> 取消了数据结构转换这一功能。或许是为了防止大数据时候二叉树建树的时间抖动问题从而取消了这一特性。直接来看下数据结构的描述：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">struct</span> <span class="n">__CFArrayDeque</span> <span class="p">{</span>
    <span class="n">uintptr_t</span> <span class="n">_leftIdx</span><span class="p">;</span> <span class="sr">//</span> <span class="err">自左开始下标位置</span>
    <span class="n">uintptr_t</span> <span class="n">_capacity</span><span class="p">;</span> <span class="sr">//</span> <span class="err">当前容量</span>
<span class="p">};</span>
<span class="n">struct</span> <span class="n">__CFArray</span> <span class="p">{</span>
    <span class="no">CFRuntimeBase</span> <span class="n">_base</span><span class="p">;</span>
    <span class="no">CFIndex</span> <span class="n">_count</span><span class="p">;</span> <span class="sr">//</span> <span class="err">元素个数</span>
    <span class="no">CFIndex</span> <span class="n">_mutations</span><span class="p">;</span> <span class="sr">//</span> <span class="err">元素抖动量</span>
    <span class="n">int32_t</span> <span class="n">_mutInProgress</span><span class="p">;</span>
    <span class="n">__strong</span> <span class="n">void</span> <span class="o">*</span><span class="n">_store</span><span class="p">;</span>
<span class="p">};</span></code></pre></div>
<p>从命名上可以看出 <code>CFArray</code> 由单一的双端队列进行实现，而且记录了一些容器信息。</p>
<h2 id="c-">C 数组的一些问题</h2>
<p>C 语言中的数组，会开辟一段连续的内存空间来进行数据的读写、存储操作。另外说一句，<strong>数组和指针并不相同</strong>。有一种被很多教材书籍上滥用的说法：一块被 malloc 过的内存空间等于一个数组。这是错误的。最简单的解释，指针需要申请一个指针区域来存储（指向）一块空间的起始位置，而数组（的头部）是对一块空间起始位置的直接访问。另外想了解更多可以看 <em><a href="http://eli.thegreenplace.net/2009/10/21/are-pointers-and-arrays-equivalent-in-c/">Are pointers and arrays equivalent in C?</a></em> 这篇博文。</p>
<p>C 中的数组最显著的缺点就是，在下标 0 处插入时，需要移动所有的元素（即 <code>memmove()</code> 函数的原理）。类似的，当删除第一个元素、在第一个元素前插入一个元素也会造成 <strong>O(n)复杂度的操作</strong> 。然而数组是常读写的容器，所以 O(n) 的操作会造成很严重的时间开销。</p>
<h2 id="cfarray--1">当前版本中 CFArray 的部分实现细节</h2>
<p>在 <a href="https://opensource.apple.com/source/CF/CF-855.17/CFArray.h.auto.html">CF-855.17</a> 中，我们可以看到当前版本的 <code>CFArray</code> 的实现。文档中对 <code>CFArray</code> 有如下的描述：</p>
<p><code>CFArray</code> 实现了一个可被指针顺序访问的紧凑容器。其值可通过整数键（索引下标）进行访问，范围从 0 至 N-1，其中 N 是数组中值的数量。称其<strong>紧凑 (compact)</strong> 的原因是该容器进行删除或插入某个值的时候，不会再内存空间中留下间隙，访问顺序仍旧按照原有键值数值大小排列，使得有效检索集合范围总是在整数范围 [0, N-1] 之中。因此，特定值的下标可能会随着其他元素插入至数组或被删除时而改变。</p>
<p>数组有两种类型：<strong>不可变(immutable)</strong> 类型在创建数组之后，不能向其添加或删除元素，而 <strong>可变(mutable)</strong> 类型可以添加或从中删除元素。可变数组的元素数量无限制（或者称只受 <code>CFArray</code> 外部的约束限制，例如可用内存空间大小）。与所有的 CoreFoundation 集合类型同理，数组将保持与元素对象的强引用关系。</p>
<p>为了进一步弄清 <code>CFArray</code> 的细节，我们来分析一下 <code>CFArray</code> 的几个操作方法：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="sr">//</span> <span class="err">通过下标查询元素值</span>
<span class="n">const</span> <span class="n">void</span> <span class="o">*</span><span class="no">CFArrayGetValueAtIndex</span><span class="p">(</span><span class="no">CFArrayRef</span> <span class="n">array</span><span class="p">,</span> <span class="no">CFIndex</span> <span class="n">idx</span><span class="p">)</span> <span class="p">{</span>
    <span class="sr">//</span> <span class="err">这个函数尚未开源</span>
    <span class="sr">//</span> <span class="err">通过给定的</span> <span class="no">CFTypeID</span> <span class="err">来验证指定元素是否匹配</span> <span class="no">Core</span> <span class="no">Foundation</span> <span class="err">桥接类</span>
    <span class="no">CF_OBJC_FUNCDISPATCHV</span><span class="p">(</span><span class="n">__kCFArrayTypeID</span><span class="p">,</span> <span class="n">const</span> <span class="n">void</span> <span class="o">*</span><span class="p">,</span> <span class="p">(</span><span class="no">NSArray</span> <span class="o">*</span><span class="p">)</span><span class="n">array</span><span class="p">,</span> <span class="ss">objectAtIndex</span><span class="p">:</span><span class="n">idx</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">尚未开源</span>
    <span class="sr">//</span> <span class="err">通过给定的</span> <span class="no">CFTypeID</span> <span class="err">来验证</span> <span class="no">Core</span> <span class="no">Foundation</span> <span class="err">类型合法性</span>
    <span class="n">__CFGenericValidateType</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">__kCFArrayTypeID</span><span class="p">);</span>
    <span class="no">CFAssert2</span><span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">idx</span> <span class="o">&amp;&amp;</span> <span class="n">idx</span> <span class="o">&lt;</span> <span class="n">__CFArrayGetCount</span><span class="p">(</span><span class="n">array</span><span class="p">),</span> <span class="n">__kCFLogAssertion</span><span class="p">,</span> <span class="s2">&quot;%s(): index (%d) out of bounds&quot;</span><span class="p">,</span> <span class="n">__PRETTY_FUNCTION__</span><span class="p">,</span> <span class="n">idx</span><span class="p">);</span>
    <span class="no">CHECK_FOR_MUTATION</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">从内存位置取出元素</span>
    <span class="k">return</span> <span class="n">__CFArrayGetBucketAtIndex</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">idx</span><span class="p">)</span><span class="o">-&gt;</span><span class="n">_item</span><span class="p">;</span>
<span class="p">}</span>
<span class="sr">//</span> <span class="err">返回查询元素的地址</span>
<span class="no">CF_INLINE</span> <span class="n">struct</span> <span class="n">__CFArrayBucket</span> <span class="o">*</span><span class="n">__CFArrayGetBucketAtIndex</span><span class="p">(</span><span class="no">CFArrayRef</span> <span class="n">array</span><span class="p">,</span> <span class="no">CFIndex</span> <span class="n">idx</span><span class="p">)</span> <span class="p">{</span>
    <span class="n">switch</span> <span class="p">(</span><span class="n">__CFArrayGetType</span><span class="p">(</span><span class="n">array</span><span class="p">))</span> <span class="p">{</span>
    <span class="sr">//</span> <span class="err">只允许两种数组类型</span>
    <span class="sr">//</span> <span class="err">不可变对应普通线性结构，可变对应双端队列</span>
    <span class="k">case</span> <span class="ss">__kCFArrayImmutable</span><span class="p">:</span>
    <span class="k">case</span> <span class="ss">__kCFArrayDeque</span><span class="p">:</span>
    <span class="sr">//</span> <span class="err">取地址再加上索引偏移量，返回元素地址</span>
	<span class="k">return</span> <span class="n">__CFArrayGetBucketsPtr</span><span class="p">(</span><span class="n">array</span><span class="p">)</span> <span class="o">+</span> <span class="n">idx</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="no">NULL</span><span class="p">;</span>
<span class="p">}</span></code></pre></div>
<p>通过索引下标查询操作中，<code>CFArray</code> 仍然继承了传统数组的连续地址空间的性质，所以其时间仍然可保持在 O(1) 复杂度，十分高效。</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">void</span> <span class="no">CFArrayInsertValueAtIndex</span><span class="p">(</span><span class="no">CFMutableArrayRef</span> <span class="n">array</span><span class="p">,</span> <span class="no">CFIndex</span> <span class="n">idx</span><span class="p">,</span> <span class="n">const</span> <span class="n">void</span> <span class="o">*</span><span class="n">value</span><span class="p">)</span> <span class="p">{</span>
    <span class="sr">//</span> <span class="err">通过给定的</span> <span class="no">CFTypeID</span> <span class="err">来验证指定元素是否匹配</span> <span class="no">Core</span> <span class="no">Foundation</span> <span class="err">桥接</span>
    <span class="no">CF_OBJC_FUNCDISPATCHV</span><span class="p">(</span><span class="n">__kCFArrayTypeID</span><span class="p">,</span> <span class="n">void</span><span class="p">,</span> <span class="p">(</span><span class="no">NSMutableArray</span> <span class="o">*</span><span class="p">)</span><span class="n">array</span><span class="p">,</span> <span class="ss">insertObject</span><span class="p">:(</span><span class="nb">id</span><span class="p">)</span><span class="n">value</span> <span class="ss">atIndex</span><span class="p">:(</span><span class="no">NSUInteger</span><span class="p">)</span><span class="n">idx</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">通过给定的</span> <span class="no">CFTypeID</span> <span class="err">来验证</span> <span class="no">Core</span> <span class="no">Foundation</span> <span class="err">类型合法性</span>
    <span class="n">__CFGenericValidateType</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">__kCFArrayTypeID</span><span class="p">);</span>
    <span class="no">CFAssert1</span><span class="p">(</span><span class="n">__CFArrayGetType</span><span class="p">(</span><span class="n">array</span><span class="p">)</span> <span class="o">!=</span> <span class="n">__kCFArrayImmutable</span><span class="p">,</span> <span class="n">__kCFLogAssertion</span><span class="p">,</span> <span class="s2">&quot;%s(): array is immutable&quot;</span><span class="p">,</span> <span class="n">__PRETTY_FUNCTION__</span><span class="p">);</span>
    <span class="no">CFAssert2</span><span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">idx</span> <span class="o">&amp;&amp;</span> <span class="n">idx</span> <span class="o">&lt;=</span> <span class="n">__CFArrayGetCount</span><span class="p">(</span><span class="n">array</span><span class="p">),</span> <span class="n">__kCFLogAssertion</span><span class="p">,</span> <span class="s2">&quot;%s(): index (%d) out of bounds&quot;</span><span class="p">,</span> <span class="n">__PRETTY_FUNCTION__</span><span class="p">,</span> <span class="n">idx</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">类型检查</span>
    <span class="no">CHECK_FOR_MUTATION</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">调用该函数进行具体的数组变动过程</span>
    <span class="n">_CFArrayReplaceValues</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="no">CFRangeMake</span><span class="p">(</span><span class="n">idx</span><span class="p">,</span> <span class="mi">0</span><span class="p">),</span> <span class="o">&amp;</span><span class="n">value</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span>
<span class="p">}</span>
<span class="sr">//</span> <span class="err">这个函数没有经过</span> <span class="no">ObjC</span> <span class="err">的调度检查，即</span> <span class="no">CF_OBJC_FUNCDISPATCHV</span> <span class="err">方法</span>
<span class="sr">//</span> <span class="err">所以为安全考虑，只能用在已经进行调度检查的函数入口之后</span>
<span class="n">void</span> <span class="n">_CFArrayReplaceValues</span><span class="p">(</span><span class="no">CFMutableArrayRef</span> <span class="n">array</span><span class="p">,</span> <span class="no">CFRange</span> <span class="n">range</span><span class="p">,</span> <span class="n">const</span> <span class="n">void</span> <span class="o">**</span><span class="n">newValues</span><span class="p">,</span> <span class="no">CFIndex</span> <span class="n">newCount</span><span class="p">)</span> <span class="p">{</span>
    <span class="sr">//</span> <span class="err">进一步类型检查</span>
    <span class="no">CHECK_FOR_MUTATION</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">加锁操作，增加自旋锁防止竞争</span>
    <span class="no">BEGIN_MUTATION</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">声明回调</span>
    <span class="n">const</span> <span class="no">CFArrayCallBacks</span> <span class="o">*</span><span class="n">cb</span><span class="p">;</span>
    <span class="sr">//</span> <span class="err">偏移下标，元素总数，数组改变后元素总数</span>
    <span class="no">CFIndex</span> <span class="n">idx</span><span class="p">,</span> <span class="n">cnt</span><span class="p">,</span> <span class="n">futureCnt</span><span class="p">;</span>
    <span class="n">const</span> <span class="n">void</span> <span class="o">**</span><span class="n">newv</span><span class="p">,</span> <span class="o">*</span><span class="n">buffer</span><span class="o">[</span><span class="mi">256</span><span class="o">]</span><span class="p">;</span>
    <span class="sr">//</span> <span class="err">获取数组中元素个数</span>
    <span class="n">cnt</span> <span class="o">=</span> <span class="n">__CFArrayGetCount</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">新数组元素总数</span> <span class="o">=</span> <span class="err">原数组元素总数</span> <span class="o">-</span> <span class="err">删除的元素个数</span> <span class="o">+</span> <span class="err">增加的元素个数</span>
    <span class="n">futureCnt</span> <span class="o">=</span> <span class="n">cnt</span> <span class="o">-</span> <span class="n">range</span><span class="o">.</span><span class="n">length</span> <span class="o">+</span> <span class="n">newCount</span><span class="p">;</span>
    <span class="no">CFAssert1</span><span class="p">(</span><span class="n">newCount</span> <span class="o">&lt;=</span> <span class="n">futureCnt</span><span class="p">,</span> <span class="n">__kCFLogAssertion</span><span class="p">,</span> <span class="s2">&quot;%s(): internal error 1&quot;</span><span class="p">,</span> <span class="n">__PRETTY_FUNCTION__</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">获取数组中定义的回调方法</span>
    <span class="n">cb</span> <span class="o">=</span> <span class="n">__CFArrayGetCallBacks</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">构造分配释放内存抽象</span>
    <span class="no">CFAllocatorRef</span> <span class="n">allocator</span> <span class="o">=</span> <span class="n">__CFGetAllocator</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">需要的情况下持有新元素，并为其分配一个临时缓冲区</span>
    <span class="sr">//</span> <span class="err">标准是新元素的个数是否超过</span><span class="mi">256</span>
    <span class="k">if</span> <span class="p">(</span><span class="no">NULL</span> <span class="o">!=</span> <span class="n">cb</span><span class="o">-&gt;</span><span class="n">retain</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">hasBeenFinalized</span><span class="p">(</span><span class="n">array</span><span class="p">))</span> <span class="p">{</span>
	<span class="n">newv</span> <span class="o">=</span> <span class="p">(</span><span class="n">newCount</span> <span class="o">&lt;=</span> <span class="mi">256</span><span class="p">)</span> <span class="p">?</span> <span class="p">(</span><span class="n">const</span> <span class="n">void</span> <span class="o">**</span><span class="p">)</span><span class="n">buffer</span> <span class="p">:</span> <span class="p">(</span><span class="n">const</span> <span class="n">void</span> <span class="o">**</span><span class="p">)</span><span class="no">CFAllocatorAllocate</span><span class="p">(</span><span class="n">kCFAllocatorSystemDefault</span><span class="p">,</span> <span class="n">newCount</span> <span class="o">*</span> <span class="n">sizeof</span><span class="p">(</span><span class="n">void</span> <span class="o">*</span><span class="p">),</span> <span class="mi">0</span><span class="p">);</span>
	<span class="k">if</span> <span class="p">(</span><span class="n">newv</span> <span class="o">!=</span> <span class="n">buffer</span> <span class="o">&amp;&amp;</span> <span class="n">__CFOASafe</span><span class="p">)</span> <span class="n">__CFSetLastAllocationEventName</span><span class="p">(</span><span class="n">newv</span><span class="p">,</span> <span class="s2">&quot;CFArray (temp)&quot;</span><span class="p">);</span>
		<span class="sr">//</span> <span class="err">为新元素增加数据缓冲区</span>
		<span class="k">for</span> <span class="p">(</span><span class="n">idx</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">idx</span> <span class="o">&lt;</span> <span class="n">newCount</span><span class="p">;</span> <span class="n">idx</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
		    <span class="n">newv</span><span class="o">[</span><span class="n">idx</span><span class="o">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">void</span> <span class="o">*</span><span class="p">)</span><span class="no">INVOKE_CALLBACK2</span><span class="p">(</span><span class="n">cb</span><span class="o">-&gt;</span><span class="n">retain</span><span class="p">,</span> <span class="n">allocator</span><span class="p">,</span> <span class="p">(</span><span class="n">void</span> <span class="o">*</span><span class="p">)</span><span class="n">newValues</span><span class="o">[</span><span class="n">idx</span><span class="o">]</span><span class="p">);</span>
		<span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
		<span class="n">newv</span> <span class="o">=</span> <span class="n">newValues</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="err">数据抖动量自加</span>
    <span class="n">array</span><span class="o">-&gt;</span><span class="n">_mutations</span><span class="o">++</span><span class="p">;</span>
    <span class="sr">//</span> <span class="err">现在将一个数组的存储区域分成了三个部分，每个部分都有可能为空</span>
    <span class="sr">//</span> <span class="ss">A</span><span class="p">:</span> <span class="err">从索引下标零的位置到小于</span> <span class="n">range</span><span class="o">.</span><span class="n">location</span> <span class="err">的区域</span>
    <span class="sr">//</span> <span class="ss">B</span><span class="p">:</span> <span class="err">传入的</span> <span class="n">range</span><span class="o">.</span><span class="n">location</span> <span class="err">区域</span>
    <span class="sr">//</span> <span class="ss">C</span><span class="p">:</span> <span class="err">从</span> <span class="n">range</span><span class="o">.</span><span class="n">location</span> <span class="o">+</span> <span class="n">range</span><span class="o">.</span><span class="n">length</span> <span class="err">到数组末尾</span>
    <span class="sr">//</span> <span class="err">需要注意的是，索引</span><span class="mi">0</span><span class="err">的位置不一定位于可用存储的最低位，当变化位置新值数量与旧值数量不同时，</span><span class="n">B</span><span class="err">区域需要先释放再替换，然后</span><span class="n">A</span><span class="err">和</span><span class="n">C</span><span class="err">中的值根据情况进行位移</span>
    <span class="k">if</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;</span> <span class="n">range</span><span class="o">.</span><span class="n">length</span><span class="p">)</span> <span class="p">{</span>
		<span class="sr">//</span> <span class="err">正常释放变化区域操作</span>
		<span class="n">__CFArrayReleaseValues</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">range</span><span class="p">,</span> <span class="kp">false</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="n">B</span> <span class="err">区现在为清空状态，需要重新填充数据</span>
    <span class="k">if</span> <span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
    	<span class="sr">//</span> <span class="err">此处隐藏了判断条件和代码。</span>
    	<span class="sr">//</span> <span class="err">大概操作是排除其他的干扰项，例如</span> <span class="n">B</span> <span class="err">区数据未完全释放等。</span>
    <span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="no">NULL</span> <span class="o">==</span> <span class="n">array</span><span class="o">-&gt;</span><span class="n">_store</span><span class="p">)</span> <span class="p">{</span>
		<span class="sr">//</span> <span class="err">通过数据的首地址引用指针来判断</span> <span class="n">B</span> <span class="err">区释放</span>
		<span class="k">if</span> <span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
			<span class="sr">//</span> <span class="err">此处隐藏了判断条件和代码</span>
			<span class="sr">//</span> <span class="err">排除干扰条件，例如</span> <span class="n">futureCnt</span> <span class="err">不合法等</span>
		<span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;=</span> <span class="n">futureCnt</span><span class="p">)</span> <span class="p">{</span>
		    <span class="sr">//</span> <span class="err">声明一个双端队列对象</span>
		    <span class="n">struct</span> <span class="n">__CFArrayDeque</span> <span class="o">*</span><span class="n">deque</span><span class="p">;</span>
		    <span class="sr">//</span> <span class="err">根据元素总数确定环状缓冲区域可载元素总个数</span>
		    <span class="no">CFIndex</span> <span class="n">capacity</span> <span class="o">=</span> <span class="n">__CFArrayDequeRoundUpCapacity</span><span class="p">(</span><span class="n">futureCnt</span><span class="p">);</span>
		    <span class="sr">//</span> <span class="err">根据元素个数确定空间分配大小</span>
		    <span class="no">CFIndex</span> <span class="n">size</span> <span class="o">=</span> <span class="n">sizeof</span><span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayDeque</span><span class="p">)</span> <span class="o">+</span> <span class="n">capacity</span> <span class="o">*</span> <span class="n">sizeof</span><span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayBucket</span><span class="p">);</span>
		    <span class="sr">//</span> <span class="err">通过缓冲区构造器来构造存储缓存</span>
		    <span class="n">deque</span> <span class="o">=</span> <span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayDeque</span> <span class="o">*</span><span class="p">)</span><span class="no">CFAllocatorAllocate</span><span class="p">((</span><span class="n">allocator</span><span class="p">),</span> <span class="n">size</span><span class="p">,</span> <span class="n">isStrongMemory</span><span class="p">(</span><span class="n">array</span><span class="p">)</span> <span class="p">?</span> <span class="n">__kCFAllocatorGCScannedMemory</span> <span class="p">:</span> <span class="mi">0</span><span class="p">);</span>
		    <span class="k">if</span> <span class="p">(</span><span class="n">__CFOASafe</span><span class="p">)</span> <span class="n">__CFSetLastAllocationEventName</span><span class="p">(</span><span class="n">deque</span><span class="p">,</span> <span class="s2">&quot;CFArray (store-deque)&quot;</span><span class="p">);</span>
		    <span class="sr">//</span> <span class="err">确定双端队列左值</span>
		    <span class="n">deque</span><span class="o">-&gt;</span><span class="n">_leftIdx</span> <span class="o">=</span> <span class="p">(</span><span class="n">capacity</span> <span class="o">-</span> <span class="n">newCount</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
		    <span class="n">deque</span><span class="o">-&gt;</span><span class="n">_capacity</span> <span class="o">=</span> <span class="n">capacity</span><span class="p">;</span>
		    <span class="n">__CFAssignWithWriteBarrier</span><span class="p">((</span><span class="n">void</span> <span class="o">**</span><span class="p">)</span><span class="o">&amp;</span><span class="n">array</span><span class="o">-&gt;</span><span class="n">_store</span><span class="p">,</span> <span class="p">(</span><span class="n">void</span> <span class="o">*</span><span class="p">)</span><span class="n">deque</span><span class="p">);</span>
		    <span class="sr">//</span> <span class="err">完成</span> <span class="n">B</span> <span class="err">区构造，安全释放数组</span>
            <span class="k">if</span> <span class="p">(</span><span class="no">CF_IS_COLLECTABLE_ALLOCATOR</span><span class="p">(</span><span class="n">allocator</span><span class="p">))</span> <span class="n">auto_zone_release</span><span class="p">(</span><span class="n">objc_collectableZone</span><span class="p">(),</span> <span class="n">deque</span><span class="p">);</span>
		<span class="p">}</span>
    <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>		<span class="sr">//</span> <span class="no">Deque</span>
	<span class="sr">//</span> <span class="err">根据</span> <span class="n">B</span> <span class="err">区元素变化，重新定位</span> <span class="n">A</span> <span class="err">和</span> <span class="n">C</span> <span class="err">区元素存储状态</span>
		<span class="k">if</span> <span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
		<span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">range</span><span class="o">.</span><span class="n">length</span> <span class="o">!=</span> <span class="n">newCount</span><span class="p">)</span> <span class="p">{</span>
		    <span class="sr">//</span> <span class="err">传入</span> <span class="n">array</span> <span class="err">引用，最终根据变化使得数组更新</span><span class="n">A</span><span class="err">、</span><span class="n">B</span><span class="err">、</span><span class="n">C</span><span class="err">分区规则</span>
		    <span class="n">__CFArrayRepositionDequeRegions</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">range</span><span class="p">,</span> <span class="n">newCount</span><span class="p">);</span>
		<span class="p">}</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="err">将区域</span><span class="n">B</span><span class="err">的新变化拷贝到</span><span class="n">B</span><span class="err">区域</span>
    <span class="k">if</span> <span class="p">(</span><span class="mi">0</span> <span class="o">&lt;</span> <span class="n">newCount</span><span class="p">)</span> <span class="p">{</span>
		<span class="k">if</span> <span class="p">(</span><span class="mi">0</span><span class="p">)</span> <span class="p">{</span>
		<span class="p">}</span> <span class="k">else</span> <span class="p">{</span>	<span class="sr">//</span> <span class="no">Deque</span>
		    <span class="sr">//</span> <span class="err">访问线性存储区</span>
		    <span class="n">struct</span> <span class="n">__CFArrayDeque</span> <span class="o">*</span><span class="n">deque</span> <span class="o">=</span> <span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayDeque</span> <span class="o">*</span><span class="p">)</span><span class="n">array</span><span class="o">-&gt;</span><span class="n">_store</span><span class="p">;</span>
		    <span class="sr">//</span> <span class="err">在原基础上，增加一段缓存区域</span>
		    <span class="n">struct</span> <span class="n">__CFArrayBucket</span> <span class="o">*</span><span class="n">raw_buckets</span> <span class="o">=</span> <span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayBucket</span> <span class="o">*</span><span class="p">)((</span><span class="n">uint8_t</span> <span class="o">*</span><span class="p">)</span><span class="n">deque</span> <span class="o">+</span> <span class="n">sizeof</span><span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayDeque</span><span class="p">));</span>
		    <span class="sr">//</span> <span class="err">更改</span><span class="n">B</span><span class="err">区域数据，类似与</span> <span class="n">memcpy</span><span class="err">，但是有写屏障</span><span class="p">(</span><span class="n">write</span> <span class="n">barrier</span><span class="p">)</span><span class="err">，线程安全</span>
		    <span class="n">objc_memmove_collectable</span><span class="p">(</span><span class="n">raw_buckets</span> <span class="o">+</span> <span class="n">deque</span><span class="o">-&gt;</span><span class="n">_leftIdx</span> <span class="o">+</span> <span class="n">range</span><span class="o">.</span><span class="n">location</span><span class="p">,</span> <span class="n">newv</span><span class="p">,</span> <span class="n">newCount</span> <span class="o">*</span> <span class="n">sizeof</span><span class="p">(</span><span class="n">struct</span> <span class="n">__CFArrayBucket</span><span class="p">));</span>
		<span class="p">}</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="err">设置新的元素个数属性</span>
    <span class="n">__CFArraySetCount</span><span class="p">(</span><span class="n">array</span><span class="p">,</span> <span class="n">futureCnt</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">释放缓存区域</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">newv</span> <span class="o">!=</span> <span class="n">buffer</span> <span class="o">&amp;&amp;</span> <span class="n">newv</span> <span class="o">!=</span> <span class="n">newValues</span><span class="p">)</span> <span class="no">CFAllocatorDeallocate</span><span class="p">(</span><span class="n">kCFAllocatorSystemDefault</span><span class="p">,</span> <span class="n">newv</span><span class="p">);</span>
    <span class="sr">//</span> <span class="err">解除线程安全保护</span>
    <span class="no">END_MUTATION</span><span class="p">(</span><span class="n">array</span><span class="p">);</span>
<span class="p">}</span></code></pre></div>
<p>在 <code>CFArray</code> 的插入元素操作中，可以很清楚的看出这是一个<strong>双端队列</strong>(dequeue)的插入元素操作，而且是一种仿照 C++ STL 标准库的存储方式，<strong>缓冲区嵌套 map 表</strong>的静态实现。用示意图来说明一下数据结构：</p>
<p><img src="http://7xwh85.com1.z0.glb.clouddn.com/cfarray-1.png" alt="cfarray-1" /></p>
<p>在 STL 中的 deque，是使用的 map 表来记录的映射关系，而在 Core Foundation 中，<code>CFArray</code> 在保证这样的二次映射关系的时候很直接地运用了二阶指针 <code>_store</code>。在修改元素的操作中，<code>CFArray</code> 也略显得暴力一些，<strong>先对数组进行大块的分区操作，再按照顺序填充数据，组合成为一块新的双端队列</strong>，例如在上图中的双端队列中，在下标为 7 的元素之前增加一个值为 <code>100</code> 的元素：</p>
<p><img src="http://7xwh85.com1.z0.glb.clouddn.com/cfarray-2.1.png" alt="cfarray-2.1" /></p>
<p>根据索引下标会找到指定部分的缓存区，将其拿出并进行重新构造。构造过程中或将其划分成 A、B、C 三个区域，B 区域是修改部分。当然如果不够的话，系统会自己进行缓存区的扩容，即 <code>CFAllocatorRef</code> 官方提供的内存分配/释放策略。</p>
<p><code>CFAllocatorRef</code> 是 Core Foundation 中的分配和释放内存的策略。多数情况下，只需要用默认分配器 <code>kCFAllocatorDefault</code> ，等价于传入 <code>NULL</code> 参数，这用会用 Core Foundation 所谓的“常规方法”来分配和释放内存。这种方法可能会有变化，我们不应该以来与任何特殊行为。用到特殊分配器的情况很少，下来是官方文档中给出的标准分配器及其功能。</p>
<table>
  <thead>
    <tr>
      <th>kCFAllocatorDefault</th>
      <th>默认分配器，与传入<code>NULL</code>等价。</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>kCFAllocatorSystemDefault</td>
      <td>原始的默认系统分配器。这个分配器用来应对万一用<code>CFAllocatorSetDefault</code>改变了默认分配器的情况，很少用到。</td>
    </tr>
    <tr>
      <td>kCFAllocatorMalloc</td>
      <td>调用<code>malloc</code>、<code>realloc</code>和<code>free</code>。如果用<code>malloc</code>创建了内存，那这个分配器对于释放<code>CFData</code>和<code>CFString</code>就很有用。</td>
    </tr>
    <tr>
      <td>kCFAllocatorMallocZone</td>
      <td>在默认的<code>malloc</code>区域中创建和释放内存。在 Mac 上开启了垃圾收集的话，这个分配器会很有用，但在 iOS 中基本上没什么用。</td>
    </tr>
    <tr>
      <td>kCFAllocatorNull</td>
      <td>什么都不做。跟<code>kCFAllocatorMalloc</code>一样，如果不想释放内存，这个分配器对于释放<code>CFData</code>和<code>CFString</code>就很有用。</td>
    </tr>
    <tr>
      <td>KCFAllocatorUseContext</td>
      <td>只有<code>CFAllocatorCreate</code>函数用到。创建<code>CFAllocator</code>时，系统需要分配内存。就像其他所有的<code>Create</code>方法，也需要一个分配器。这个特殊的分配器告诉<code>CFAllocatorCreate</code>用传入的函数来分配<code>CFAllocator</code>。</td>
    </tr>
  </tbody>
</table>
<p>在 <code>_CFArrayReplaceValues</code> 方法中的最后一个判断：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="k">if</span> <span class="p">(</span><span class="n">newv</span> <span class="o">!=</span> <span class="n">buffer</span> <span class="o">&amp;&amp;</span> <span class="n">newv</span> <span class="o">!=</span> <span class="n">newValues</span><span class="p">)</span>
	<span class="no">CFAllocatorDeallocate</span><span class="p">(</span><span class="n">kCFAllocatorSystemDefault</span><span class="p">,</span> <span class="n">newv</span><span class="p">);</span></code></pre></div>
<p>会检查一下缓存区的数量问题，如果数量过多会释放掉多余的缓存区。这是因为这个方法具有通用性，不仅仅可以使用在插入元素操作，在增加(<code>CFArrayAppendValue</code>)、替换(<code>CFArrayReplaceValues</code>)、删除(<code>CFArrayRemoveValueAtIndex</code>)操作均可使用。由于将数据结构采取分块管理，所以时间分摊，复杂度大幅度降低。所以，我们看到 <code>CFArray</code> 的时间复杂度在查询、增添元素操作中均有较高的水平。</p>
<p>而在 <code>NSMutableArray</code> 的实现中，苹果为了解决移动端的小内存特点，使用 <code>CFArray</code> 中在两端增加可扩充的缓存区则会造成大量的浪费。在 <a href="http://blog.joyingx.me/2015/05/03/NSMutableArray%20%E5%8E%9F%E7%90%86%E6%8F%AD%E9%9C%B2/">NSMutableArray原理揭露</a> 一文中使用逆向的思路，挖掘 <code>NSMutableArray</code> 的实现原理，其做法是使用<em>环形缓冲区</em>对缓存部分做到最大化的压缩，这是苹果针对于移动设备的局限而提出的方案。</p>
<h2 id="section">参考资料：</h2>
<p><a href="https://www.mikeash.com/pyblog/friday-qa-2012-03-09-lets-build-nsmutablearray.html">Let’s Build NSMutableArray</a></p>
<p><a href="https://github.com/opensource-apple/CF/blob/master/CFArray.h">GNUStep · NSArray</a></p>
<p><a href="http://stackoverflow.com/questions/22591296/what-is-the-data-structure-behind-nsmutablearray">What is the data structure behind NSMutableArray?</a></p>
<p><a href="https://opensource.apple.com/source/CF/CF-855.17/CFArray.c">Apple Source Code - CF-855.17</a></p>
  <footer class="post-footer">
    <section class="author">
      <h4>Desgard_Duan</h4>
      <p>I write many code to write less code.💻</p>
    </section>
<aside class="share">
  <h4>Share this.</h4>
  <a href="http://twitter.com/share?text=《CFArray 的历史渊源及实现原理》 -- Guardia · 瓜地&amp;url=https://www.desgard.com/CFArray/"
  onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-twitter-square"></i>
  </a>
  <a href="http://v.t.sina.com.cn/share/share.php?url=https://www.desgard.com/CFArray/&amp;title=《CFArray 的历史渊源及实现原理》 —— Guardia · 瓜地" onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-weibo"></i>
  </a>
</aside>
      <hr>
<aside id="comments" class="disqus">
  <div id="container"></div>
  <!-- <link rel="stylesheet" href="/assets/css/gitment.css">
  <script src="https://imsun.github.io/gitment/dist/gitment.browser.js"></script>
  <script>
  var gitment = new Gitment({
    id: "https://www.desgard.com/CFArray/", 
    owner: 'Desgard',
    repo: 'desgard.github.com',
    oauth: {
      client_id: 'e2612df42f3f2a83e71c',
      client_secret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
    },
  })
  gitment.render('container')
  </script> -->
<link rel="stylesheet" href="/assets/css/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id='gitalk-container'></div>
<script>
    const gitalk = new Gitalk({
        id: "https://www.desgard.com/CFArray/", 
        clientID: 'e2612df42f3f2a83e71c',
        clientSecret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
        repo: 'desgard.github.com',
        owner: 'Desgard',
        admin: ['Desgard'],
        // facebook-like distraction free mode
        distractionFreeMode: false
    })
    gitalk.render('gitalk-container')
</script>
</aside>
  </footer>
</article>
    </main>
<footer class="footer">
  <div class="container">
    <ul class="icons">
      <li>
        <a href="https://github.com/desgard" class="icon-github" target="_blank">
          <i class="fa fa-github"></i>
        </a>
      </li>
      <li>
        <a href="https://www.facebook.com/desgard.duan" class="icon-facebook" target="_blank">
          <i class="fa fa-facebook"></i>
        </a>
      </li>
      <li>
        <a href="https://twitter.com/Desgard_Duan" class="icon-twitter" target="_blank">
          <i class="fa fa-twitter"></i>
        </a>
      </li>
      <li>
        <a href="https://stackoverflow.com/users/6119149/desgard-duan" class="icon-github" target="_blank">
          <i class="fa fa-stack-overflow"></i>
        </a>
      </li>
      <li>
        <a href="https://weibo.com/desgard" class="icon-instagram" target="_blank">
          <i class="fa fa-weibo"></i>
        </a>
      </li>
    </ul>
    <p>
      <q>I write many code to write less code.💻</q>
      <small>– Gua</small>
    </p>
    <small class="clearfix">
      Powered by <a href="http://jekyllrb.com" target="_blank">Jekyll</a> • <a href="https://github.com/desgard" target="_blank">Open source <i class="fa fa-heart"></i></a>
    </small>
  </div>
</footer>
<a class="scroll-up fa fa-chevron-up bounce" href="#" data-position="0"></a>
<div id="modalSearch" class="modal">
  <div class="modal__overlay"></div>
  <div class="modal__content">
    <a href="#!" class="modal-close" data-modal-close>&times;</a>
    <div class="search-container">
      <input type="text" id="search-input" placeholder="Search articles">
      <ul id="results-container"></ul>
    </div>
  </div>
</div>
    <script src="/assets/main-52d417e8a6ff9f5b168386d37c96338a.js"></script>
  </body>
  <script>
    var link = "" ;
    var os = function() {  
      var ua = navigator.userAgent,  
      isWindowsPhone = /(?:Windows Phone)/.test(ua),  
      isSymbian = /(?:SymbianOS)/.test(ua) || isWindowsPhone,   
      isAndroid = /(?:Android)/.test(ua),   
      isFireFox = /(?:Firefox)/.test(ua),   
      isChrome = /(?:Chrome|CriOS)/.test(ua),  
      isTablet = /(?:iPad|PlayBook)/.test(ua) || (isAndroid && !/(?:Mobile)/.test(ua)) || (isFireFox && /(?:Tablet)/.test(ua)),  
      isPhone = /(?:iPhone)/.test(ua) && !isTablet,  
      isPc = !isPhone && !isAndroid && !isSymbian;  
      return {  
        isTablet: isTablet,  
        isPhone: isPhone,  
        isAndroid : isAndroid,  
        isPc : isPc  
      };  
    }();  
    if (link.length > 0) {
      if (os.isAndroid || os.isPhone) {
        location.replace(link);
      }
    }
  </script>
</html>